var monthLengths = [31, , 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
var dayOfWeekPrefixes = [
  "Sun", "Mon", "Tues", "Wednes", "Thurs", "Fri", "Satur"];
var monthNames = [
  "Jan.", "Feb.", "Mar.", "Apr.", "May", "June", "July", "Aug", "Sep.",
  "Oct.", "Nov.", "Dec."];

var FREQ_DAILY = 0;
var FREQ_WEEKLY = 1;
var FREQ_MONTHLY = 2;
var FREQ_YEARLY = 3;

function isLeapYear(year) {
  return !((year % 4) || (!(year % 100) && (year % 400)));
}

function countDaysInMonth(year, month) {
  return month === 1 ? (isLeapYear(year) ? 29 : 28) : monthLengths[month];
}

/**
 * Convert a date value into a number of days since epoch,
 * which is the imaginary beginning of year zero in a hypothetical
 * backward extension of the Gregorian calendar through time.
 * See Calendrical Calculations, Reingold and Dershowitz.
 */
function fixedFromGregorian(year, month, day) {
  var yearM1 = year - 1;
  var monthP1 = month + 1;
  return 365 * yearM1 +
      ((yearM1 / 4) | 0) -
      ((yearM1 / 100) | 0) +
      ((yearM1 / 400) | 0) +
      (((367 * monthP1 - 362) / 12) | 0) +
      (monthP1 <= 2 ? 0 : (isLeapYear(year) ? -1 : -2)) +
      day;
}

function daysBetween(a, b) {
  var ya = a.getUTCFullYear();
  var ma = a.getUTCMonth();
  var da = a.getUTCDate();
  var yb = b.getUTCFullYear();
  var mb = b.getUTCMonth();
  var db = b.getUTCDate();
  if (ya === yb && ma === mb) { return da - db; }
  return fixedFromGregorian(ya, ma, da) - fixedFromGregorian(yb, mb, db);
}


function date(year, month, day) {
  while (true) {
    if (month >= 12) {
      month -= 12;
      year += 1;
    } else if (month < 0) {
      month += 12;
      year -= 1;
    } else if (day <= 0) {
      if (month === 0) {
        day += 31;
        month = 11;
        year -= 1;
      } else {
        month -= 1;
        day += countDaysInMonth(year, month);
      } 
    } else if (day > 28) {
      var n = countDaysInMonth(year, month);
      if (day > n) {
        day -= n;
        month += 1;
      } else {
        break;
      }
    } else {
      break;
    }
  }
  return new Date(Date.UTC(year, month, day));
}

function startOfWeek(d, wkst) {
  return date(
      d.getUTCFullYear(),
      d.getUTCMonth(),
      d.getUTCDate() - ((7 + d.getUTCDay() - wkst) % 7));
}

/**
 * Given a date, returns the date that is at most n periods of length freq
 * forward of it and starts a period of size freq.
 */
function addPeriod(d, freq, n, wkst) {
  var year = d.getUTCFullYear();
  var month = d.getUTCMonth();
  var day = d.getUTCDate();
  switch (freq) {
    case FREQ_DAILY:
      day += n;
      break;
    case FREQ_WEEKLY:
      day -= (7 + (d.getUTCDay() - wkst || 0)) % 7;  // Shift to start of week.
      day += 7 * n;
      break;
    case FREQ_MONTHLY:
      day = 1;  // Shift to start of month.
      month += n;
      break;
    case FREQ_YEARLY:
      day = month = 1;  // Shift to start of year.
      year += n;
      break;
  }
  var out = date(year, month, day);
  var delta = out - d;
  if (delta && (delta > 0) !== (n > 0)) {
    throw new Error(
      "Over or underflow, probably of the year field. " + d + " -> " + out);
  }
  return out;
}

function uniqInts(arr) {
  var value_set = {};
  var out = [];
  for (var i = 0, n = arr.length; i < n; ++i) {
    var x = arr[i];
    var xi = +x;
    if (value_set[xi] === value_set) { continue; }
    value_set[xi] = value_set;
    out.push(x);
  }
  out.sort(function (a, b) { a = +a; b = +b; return a - b; });
  return out;
}

function fmtDate(d) {
  return d.getUTCFullYear() + "-" + (d.getUTCMonth()+1) + "-" + d.getUTCDate();
}
